package com.my.study.structures.search;

import java.util.Arrays;

/**
 * @author Carlos
 * @version 1.0
 * @Description 斐波那契查找算法
 *
 * <p>
 *    mid值不在是中间的某个值，而是位于黄金分割点附近，即mid = low + f[k-1] - 1
 *
 * <p>
 * 对于f[k-1] - 1的理解：
 * 由菲波那切数列f[k] = f[K-1]+f[k-2]的性质，可知：f[k]-1 = (f[K-1] -1 ) + (f[k-2] - 1) + 1
 *
 *
 *
 * @date 2021/7/28 23:11
 **/
public class FibonacciSearch {

    static int MAX_SIZE = 20;


    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};

        System.out.println(search(arr, 1));

    }


    /**
     * 构建一个菲波那切数列
     * <p>
     * int mid = low + F(k-1) - 1
     *
     * @return
     */
    private static int[] fib() {
        int[] fib = new int[MAX_SIZE];
        fib[0] = 1;
        fib[1] = 1;

        for (int i = 2; i < MAX_SIZE; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib;
    }


    public static int search(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        // 代表斐波那契数列分割数值的下标
        int k = 0;
        int mid = 0;
        int[] f = fib();
        // 获取斐波那契分割数值的下标
        while (high > f[k] - 1) {
            k++;
        }

        // 因为f[k]的值可能大于数值arr[]的长度，因此我们使用Arrays类构造一个新数组，并指向temp[]
        // 不足部分使用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 修改填充值，改为arr[high]的值
        // {1, 8, 10, 89, 1000, 1234, 0, 0}  => {1, 8, 10, 89, 1000, 1234, 1234, 1234}
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }

        while (low <= high) {
            mid = low + f[k - 1] - 1;
            // 向左边查找
            if (key < temp[mid]) {
                high = mid - 1;

                k--;
            }
            // 向右边查找
            else if (key > temp[mid]) {
                low = mid + 1;

                k -= 2;
            } else {
                return Math.min(mid, high);
            }
        }

        return -1;

    }

}
